1. Field of the Invention
This invention relates to improvements in computer systems, and more particularly to improvements in a computer system of the type in which memory management operations are enabled to be performed independently of and in parallel with an associated central processing unit (hereinafter referred to as the CPU).
2. Background Information
The development of storage management systems has a long history with many related branches of research. Over the years, a great deal of attention has been given to the allocation and deal location of memory structures. Many memory structures, for example, are shown by Deitel, H. M., An Introduction to Operating Systems, Addison-Wesley, Mass., Chapter 7, 1982. Other major issues are discussed by Knuth, D., The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Addison-Wesley, Reading, Mass., 1968. The invention herein described is concerned with computer systems having heap managed memories which are automatically managed. The functions which are automatically managed can include, for instance, memory allocation, deallocation, compaction, garbage collection, and so forth, as will become apparent. Heap managed means that the memory is allocated and freed (either explicitly or implicitly) without regard to the temporal order or the size of the memory unit under consideration. An automatically managed memory refers to a memory which is selfreclaiming garbage collected. A garbage collected memory is one in which usable memory is automatically reclaimed, and the memory may be reorganized from time to time to efficiently utilize the space of the memory, as needed. A survey of garbage collection techniques and related background materials is presented by Cohen, J. "Garbage Collecton of Linked Data Structures", Computing Surveys, Vol. 13, No. 3, September, 1981, pp. 341-367. P. Bishop discusses garbage collection in very large address spaces in "Garbage Collection in a Very Large Address Space", Massachusetts Institute of Technology, Working Paper 111, September, 1975.
Presently, implementations of computer languages, such as Lisp, and to a lesser extent, Pascal and Ada, support such heap allocated memories (Lisp implementations supporting garbage collected memory, as well). In traditional compiler architectures where the memory allocation, de-allocation, garbage collection and compaction are provided, normally the language runtime support and the complier used have the responsibility for the garbage collection and compaction. However, occasionally, and unfortunately, the application programmers end up with the responsibility of storage management. If a virtual memory system is provided, it is normally the responsibility of the hardware and operating system to manage the virtual memory system. Typically, for example, the operating system will use some type of demand paged, least recently used (LRU) scheme for determining when and how to move pages between main memory and the backing store, and the garbage collector specifies which pages will be needed or which will no longer be needed. This leads to, at best, a suboptimal use of machine resources and poor performance.
"Knowledge bases" are becoming of interest with the rapid development of artificial intelligence (AI) technology. Knowledge bases are large data bases for use, for instance, in containing large and complex information structures requiring dynamic organization. See, for example, Suwa, M., et al, "Knowledge Base Mechanisms", Preliminary Report on Fifth Generation Computer Systems, ICOT, 1980. Examples of some large data bases under consideration or implemented include, for instance, data bases which contain legal information, verbatim case reports, medical information for use in diagnosing possible diseases which present particular symptoms, certain patent information including abstracts, claims, and assignment information, and many engineering data bases, including CAD/CAM data bases and the like. In such data bases, it is often desirable to search through sometimes millions of words and characters to find the few, if any, occurrences of a particular set of words and characters, then identify a particular record (case, patent, diagnosis, etc.) related to the words and characters. The management or manipulation of such large data bases is usually the responsibility of presently available specialized machine software. Such software is usually referred to as the "data base manager".
Thus, in systems available today, storage is usually managed in hardware, operating system, language implementations, data bases, and even application programs. The heap management and garbage collection is managed by the run-time support and compiler, the virtual memory by the operating system, and the knowledge base and data base by the data base manager. There are a large number of techniques in use, which, at best, result in local optimizations, but more often, do not work together symbiotically. These techniques are often difficult for the individual programmer to understand or manage.
The speed of memory allocation presents a difficult problem if memory blocks are not of constant size or are not managed in the last-in first-out (LIFO) discipline. Also, the time delay between a block of memory becoming inaccessible (that is, unreachable by any program) and the time that its space is available for reuse is a frequently encountered problem. Additionally, the overall size of a virtual memory space is often of concern, since garbage collection costs increase with the size of the space being collected not with the amount of garbage being reclaimed. Finally, security or integrity is a significant problem, because programs can either intentionally or through inadvertence overwrite or destroy data or structure (i.e., pointers).